﻿using System.Text;
using TSP.Algorithm;

namespace TSP;

/// <summary>
/// 旅行商问题TSP算法计算器
/// </summary>
public class TSPCalculator
{
    /// <summary>
    /// 构造TSP计算器实例
    /// </summary>
    /// <param name="cityNumber">城市数量</param>
    /// <param name="costs">城市间的耗费（按照邻接矩阵上三角区域从上到下、从左到右排序）</param>
    /// <exception cref="ArgumentException">当distances的长度 != cityNumber * (cityNumber - 1) / 2时抛出异常</exception>
    public TSPCalculator(byte cityNumber, params double[] costs)
    {
        if (costs.Length != cityNumber * (cityNumber - 1) / 2)
            throw new ArgumentException("城市数量与距离数量不符");
        else
        {
            Cities = new List<City>(cityNumber);
            for (byte i = 0; i < cityNumber; i++)
                Cities.Add(new City(i));
            Distances = new double[cityNumber, cityNumber];
            byte flag = 0;
            for (int i = 0; i < cityNumber - 1; i++)
            {
                for (int j = 0; j < cityNumber - 1 - i; j++)
                {
                    Distances[i, j + 1 + i] = costs[flag];
                    Distances[j + 1 + i, i] = costs[flag];
                    flag++;
                }
            }
            City.Distances = Distances;
        }
    }

    /// <summary>
    /// 城市列表
    /// </summary>
    public List<City> Cities { get; private set; } = new List<City>();

    private double[,] Distances { get; set; }

    internal static double MutRate { get; set; } = 0.03;

    internal static int Elitism { get; set; } = 6;

    internal static int PopSize { get; set; } = 60;

    /// <summary>
    /// 计算最短路径
    /// </summary>
    /// <param name="iterationNumber">遗传算法迭代次数</param>
    /// <returns>最短路径城市ID序列与最短距离</returns>
    public async Task<(byte[] ResultRoute, double TotalCost)> CalculateAsync(int iterationNumber)
    {
        return await Task.Run(() =>
        {
            var p = Population.Randomized(new Tour(Cities), PopSize);
            for (int i = 0; i < iterationNumber; i++)
                p = p.Evolve();
            var bestTour = p.FindBest();
            return (FormatRoute(bestTour.CityIDSeries), bestTour.Distance);
        });
    }

    private static byte[] FormatRoute(byte[] route)
    {
        var result = new byte[route.Length];
        var anotherresult = new byte[route.Length];
        var start = GetStartIndex(route);
        for (int i = 0; i < route.Length; i++)
        {
            result[i] = route[(i + start) % route.Length];
        }

        result.CopyTo(anotherresult,0);
        Array.Reverse(anotherresult, 1, result.Length - 1);

        var startP = new City(0);
        return startP.DistanceTo(new City(result[1])) <= startP.DistanceTo(new City(anotherresult[1])) ? result : anotherresult;
    }

    private static byte GetStartIndex(byte[] route)
    {
        for (int i = 0; i < route.Length; i++)
        {
            if (route[i] is 0)
                return (byte)i;
        }
        throw new ArgumentException("没有找到起点");
    }

    public override string ToString()
    {
        var sb = new StringBuilder();
        int c = Cities.Count;
        sb.AppendLine("CityNumber: " + c);
        for (int i = 0; i < c; i++)
        {
            for (int j = 0; j < c; j++)
                sb.Append(Distances[i, j] + " ");
            sb.AppendLine();
        }
        return sb.ToString();
    }
}
